package com.zhz.leetcode;

/**
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串""。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 * <p>
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= strs.length <= 200
 * 0 <= strs[i].length <= 200
 * strs[i] 仅由小写英文字母组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestCommonPrefix14 {

    public static void main(String[] args) {
        LongestCommonPrefix14 m = new LongestCommonPrefix14();
        String[] strs = {"flower","","flight"};
        String s = m.longestCommonPrefix1(strs);
        System.out.println(s);
    }

    /**
     * 暴力解法
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }
        StringBuilder s = new StringBuilder();
        for (int i = 0; i <= 200; i++) {
            if (strs[0].length() <= i) {
                return s.toString();
            }
            char a = strs[0].charAt(i);
            for (int j = 0; j < strs.length; j++) {
                if (strs[j].length() <= i || strs[j].charAt(i) != a) {
                    return s.toString();
                }
            }
            s.append(a);
        }
        return s.toString();
    }


    /**
     * 官方思路：
     * 从前往后比较，
     * 先[0]和[1]比较取出最长公共前缀
     * 然后最长公共前缀再和[2]比较，再取出最长公共前缀
     * 以此类推...
     * 如果遇到空串，则直接退出。
     */
    public String longestCommonPrefix1(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }
        String s = strs[0];
        for (int i = 1; i < strs.length; i++) {
            s = test(s, strs[i]);
            if (s.length() == 0) {
                return "";
            }
        }
        return s;
    }

    /**
     * 两个字符串取出最长公共前缀
     */
    public String test(String str1, String str2) {
        int len = Math.min(str1.length(), str2.length());
        for (int i = 0; i < len; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                return str1.substring(0, i);
            }
        }
        return str1.substring(0, len);
    }

}
